#include <stdio.h>
#include <stdlib.h>

#define MAXEDGE 20
#define MAXVEX 10

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

typedef struct
{
	int numVertexes, numEdges;		/* 图中当前的顶点数和边数 */
}MGraph;

int Find(int *parent, int f)
{
	while (parent[f]>0)
		f = parent[f];
	return f;
}

void MiniSpanTree_Kruskal(MGraph G, Edge edges[MAXEDGE])
{
	int i, n, m;
	int parent[MAXVEX];
	for (i = 0; i < G.numVertexes; ++i)
		parent[i] = 0;
	for (i = 0; i < G.numEdges; ++i)
	{
		n = Find(parent, edges[i].begin);
		m = Find(parent, edges[i].end);
		if (n != m)
		{
			parent[n] = m;
			printf("(%d, %d) %d \n", edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
}


int main()
{
    int i;
    Edge edges[MAXEDGE];
    int bew[15][3] =
    {
        {4, 7, 7},
        {2, 8, 8},
        {0, 1, 10},
        {0, 5, 11},
        {1, 8, 12},
        {3, 7, 16},
        {1, 6, 16},
        {5, 6, 17},
        {1, 2, 18},
        {6, 7, 19},
        {3, 4, 20},
        {3, 8, 21},
        {2, 3, 22},
        {3, 6, 24},
        {4, 5, 26}
    };
    MGraph G;
    G.numVertexes = 9;
    G.numEdges = 15;

    for(i=0; i < 15; i++)
    {
        edges[i].begin = bew[i][0];
        edges[i].end = bew[i][1];
        edges[i].weight = bew[i][2];
    }

    MiniSpanTree_Kruskal(G, edges);

    return 0;
}










